class Solution {
    /*  
        思路1：二进制思想
        求子集，对于5（101），我们可以看做对于每个位置的元素分别是
        【取，不取，取】
    */
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        int tot = 1 << len; // 等价于pow(2,nums.length)
        for(int num=0; num<tot; num++){
            List list = new ArrayList<>();
            for(int k=0; k<len; k++){
                int tmp = (num >> k) & 1; //表示num的二进制下第k位的值
                if( tmp==1 ){
                    list.add(nums[k]);
                }
            }
            ans.add(new ArrayList<>(list));
        }
        return ans;
    }
}

class Solution {
    /*
        回溯
    */
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return ans;
    }
    public void dfs(int[] nums,int index){
        // 跳出边界
        if( index>=nums.length ){
            ans.add(new ArrayList<>(list));
            return;
        }
        // 分叉1：不选择nums[idnex]]加入子集
        dfs(nums,index+1);

        // 分叉2：选择nums[index]加入子集
        list.add(nums[index]);
        dfs(nums,index+1);
        list.remove(list.size()-1);
    }
}